这篇文章可谓来之不易, 因为太长时间没写了, 中间换了系统, 之前配好的环境都没了, 就费了很大力气又装了一边… 这里就不详细说明了

这里主要记录一下 ubuntu 下挂载 Windows 分区的问题

mount

既然是挂载, 就先说一下这个命令, 一般来说, 格式是这样的

mount dir

dir 就是要挂载的分区所在的地方, 一般是类似 /dev/sda1 这样的地址

但是记住每个 windows 分区对应那个sda 后面的数字太麻烦了, 直接根据分区挂载:

mount -L label_name_here /path/to/mount/point

或者, 查一下 LABEL 和 NAME 的对应关系,

使用 list block

1
2
3
4
5
6
7
8
9
10
11
12
13
14

$ sudo lsblk -o NAME,LABEL
NAME                    LABEL
sda                     
├─sda1                  System Reserved
├─sda2                  windows
├─sda3                  ubuntu
├─sda4                  
├─sda5                  arch
├─sda6                  
│ └─lvmg-homelvm (dm-0) homelb
└─sda7                  
sdb                     
└─sdb1                  
  └─lvmg-homelvm (dm-0) homelb

使用 block id

1
2
3
4
5
6
7
8
9
10

sudo blkid -o list


device          fs_type  label     mount point         UUID
----------------------------------------------------------------------------------
/dev/sda1       ntfs     WINRE_DRV (not mounted)       604C3A6A4C3A3B5C
/dev/sda2       vfat     SYSTEM_DRV (not mounted)      6C3C-72E3
/dev/sda3       vfat     LRS_ESP   (not mounted)       5240-1BEE
/dev/sda5       ntfs     Windows8_OS /media/Win8       A47A42FF7A42CDAC
/dev/sda6       ntfs     Daten     /media/Daten        72860971860936DF

自动挂载

windows 的分区是不会在开机的时候自动被挂载的, 想自动挂载的话需要修改系统文件 /etc/fstab

其中针对每个分区可以进行挂载的参数配置, 如下:

UUID=AA8C58748C583CCF /media/harry/code ntfs umask=0033,gid=1000,uid=1000 0 1

UUID是磁盘的id, 后面是挂载地址, 分区格式, 参数, 等等..

这里说一下参数

umask

user mask

是打开文件之后文件去掉的读写权限

0 代表什么权限都不去掉, 也就是读写执行都有

1 代表去掉执行 2 代表去掉写 4 代表去掉读

它们互相组合就得到了总共需要去掉的权限

033 就代表了文件所有者有所有权限, 同组或者其他组的其他人只能读

那么, 从哪里减去呢?

是从默认权限里面减去, 文件的默认权限是 666, 文件夹的默认权限是 777

• 创建文件时：(-rw-rw-rw-) - (—–w–w-) ==> -rw-r–r–
• 创建目录时：(drwxrwxrwx) - (d—-w–w-) ==> drwxr-xr-x

source

比较 tricky 的一点, 挂载一个windows硬盘的时候, 默认是给所有文件所有权限的

如果只想把文件的 执行 权限去掉的话, 就不能使用 umask 来控制permission了(那样会把文件夹的执行权限也去掉..从而访问不了任何文件)

这里就要引进 fmask 和 dmask 了

fmask dmask

很简单 file mask , 和 directory mask, 分别控制文件和文件夹需要去掉的权限

gid uid

挂载这个分区中所有的文件的所有者, 组 1000表示默认用户

另外也可以手动给mount加参数挂载

 mount -t deviceFileFormat -o umask=filePermissons,gid=ownerGroupID,uid=ownerID /device /mountpoint

所以,最后的配置变成了这样

# mount windows partition code volumn UUID=AA8C58748C583CCF /media/harry/code ntfs uid=1000,gid=1000,dmask=022,fmask=133 0 1

这是一篇一直想写的总结. 主要是复习的时候详细复习(这里应该说是学习了..)了一下最短路径问题. 发现当年学的还有很多不足.. 很多算法没学过,学过的算法的局限性我也不知道.

就像当年数据结构上机,练习dijkstra算法,虽然我自己敲了出来,但是学长问我这个能不能处理负权边的问题的时候我还是不知道..

这里就以负权边为索引详细说一下几个最短路径算法..

1. Dijkstra算法

这个应该比较熟悉了,所有的涉及到最短路径的问题都会提到这个算法. 算法原理是贪心 解决单源最短路径问题

先选择一个源点,也就是路径的起点. 然后重复 k 轮,每一轮添加一个点到目前生成的树里面,所以 k 是除源点外节点的数目 每一轮中分为两步

1. 选择 : 选择源点到达距离最短的点当做下一个加入生成树里面的点
2. 更新 : 由刚刚选择的点更新源点到每个点的距离

其中.选择这一步跟时间复杂度有点关系

1. 比较朴素的方法,既然要选最小的,那就遍历一遍
   • 这种方法在图比较稠密的时候比较好用,时间复杂度为:
2. 既然要找最小的,建一个最小堆就可以了,这样时间复杂度好像比较低
   • 实际上这样做的话比较复杂,时间复杂度也不一定低.
   • 复杂点 1 在堆里面要存一对元素(pair),因为我们需要距离这个值来进行比较,维护这个堆,还需要最小的距离对应的节点的编号,因为后面我们需要找到这个节点进行更新
   • 复杂点 2 在于这个堆不是一成不变的,而需要更新,每次更新的时候都涉及堆结构的变化,会带来额外的复杂度
   • 这种方法在图比较稀疏的时候比较好用,时间复杂度为:

最后,这个算法没有办法解决负权边的问题 因为上文提到,这个算法逐步生成一棵树的,而每一步新生成的节点都代表了源点到它的最短路径. 如果有负权边的话,上面那句话就无法保证,有可能会出现后面的一条负权边导致前面已经生成完毕的树里面的某个点遭到破坏

2. Bellman-Ford算法

这个算法有改进,权值可以为负

dist k[u] 代表最多经过 k 条边,源点到 u 的最短距离

dist n[u] 就是源点到 u 的最短距离, n 为顶点数(因为最短路径边数目小于顶点数,没有负权环)

可以得到推导式

dist k[u] = min{dist k-1[u], min{dist k-1[j] + E[j][u] } }

由源点最多经过 k 条边,到 u 的最短距离是 { 最多经过 k-1 条边的最短距离 } 和 { 最多经过 k-1 条边到某个边的最短距离加上这个边到 u 的距离 }里面更小的那个

伪代码如下

1
2
3
4
5

for(k = 2 : n)
    for(u = 0 : n)
        for(i = 0:n)
            if(E[i][u] > 0 && dist[u] > E[i][u] + dist[i])
                dist[u] = E[i][u] + dist[i]

上面提到了,这个算法不允许图中有负权环 因为出现了负权环,就不存在最短路径问题了,一直在负权环上面循环可以使路径趋近于无穷小..

3.发现负权环

上面提到了负权环,如何判断图中有没有负权环呢?

先看看如何发现环 可以进行一波深度优先搜索,如果发现搜索的过程中搜索到了已经搜到了的元素,就有环 或者进行一下拓扑排序,如果运行到最后还有元素,就能判断有环

由于和题目不太相关,这里先不多说了

4.Floyd算法

上面说了单源最短路径的算法,这里说一个多源的,就是求出整个图上每两点之间的最短路径

A ij[k] 代表从 i 到 j ,中转点序号小于等于 k 的最短路径

A ij[n] 就是从 i 到 j 的最短路径, n 为节点的数目,也就是节点序号的最大值

可以得到推导式

A ij[k] = min{ A ij[k-1] , A ik[k-1] + A kj[k-1]}

从 i 到 j ,中转点序号小于等于 k 的最短路径等于 { 中转点序号小于 k-1 的最短路径 } 和 { 中转点序号最大为 k 的最短路径(中转点包含k) }里面最小的一个

总结结束.. 今天看到了一个有趣的单词 redraw re-draw 重画 我一开始看成了 red-raw 红红的原始的..

这是一篇关于保研的总结,记录我可能持续了整个大三的保研之路..

但是在此之前,先说个技术问题. 关于powershell的. 一开始在windows上面用git是直接下了个windows版的github,桌面版还挺好用的.随之而来的还有一个叫gitshell的东西,就是一个windows上用的shell,里面预装了git,能直接用git的各种指令,感觉还挺好. 后来我的windows升级到win10之后这个就出了问题,中文输入输不进去后来查了一下是页面编码的问题. 原因是这个shell编码由原来的GBK变成了UTF8,识别不了中文了,只要用

>>>chcp 936

就可以了,这个是将当前页的编码改成936(GBK),change current code page 但是用 rake new_post 发博客的时候还是会遇到错误

(UTF-8 regexp with GBK string)

这个只要把字体改一下就可以,改一个可以支持中文的字体

下面进入正文

准备

之前不确定要读研,说实话直到找实习不顺利我才确定我这水平还是先读个研来的比较妥当. 但是我从大三一开始就做了一些相关的准备,这些准备到了最后也是确实起到了很大的帮助. 其实全部的准备工作就是刷OJ,一开始想法很简单,找工作算法能力也很重要,保研的话也会有机试,直接刷一下OJ锻炼一下算法能力也是很好的.

没想到我还挺喜欢刷题的,有空了就去leetcode上面做题,遇到难题可能好几天也想不出来,最后忍不住了去看别人分享的答案,毕竟这是少数,大多数题目思考一下还是能想出来的. 到最后,我在某一个时间点把leetcode上的题做完了(后来没怎么做过leetcode,新题都没做),通过代码的积累,算法也提升了一些.

做完了leetcode又去poj上面做题,但是上面题太多,就找了个经验贴,按上面的顺序做题,做了几天又发现了一个保研机试的oj,九度oj,上面的题都比较简单.用来练手热身都很合适,但是后来也放弃了.

直到我遇到了51nod这个oj,这个oj真的非常棒,中国社区,有很多活跃的大神在上面,而且题目有难度分级,还有一些教程,尤其是动态规划的,对于我这种从来没接受过专业ACM训练的人来说真是再好不过了.事实上,这个动态规划的训练到后来真的帮了我很多.

中间还兴致勃勃地报名了微软的编程之美,水了件T恤回来.

粗略算下来,oj上面的题我也刷了三四百道,逐渐对算法理解也更多,更深刻了.这些东西想想也真的是教不来,只能自己慢慢做,慢慢体会.

除了刷OJ之外,我也没进行其他的复习,也就是数据结构与算法,我找了好几本书,看了很多,也对以前学过的算法有了更多的理解. 复习的时候看的书很多,一个算法一本书上说的不明白我就去看另一本.不过主要看的就是 英文的<数据结构与算法分析:C语言描述>,看算法还能练练英语,还有就是学校图书馆借的Sedgewick的<算法>,里面对于图那一块讲的挺好的.

到现在记忆比较深的就是最短路径算法,记得当时上机给学长检查,学长为了检查代码是不是自己写的都要问几个问题,这个我大学所有的代码都是自己写的,但是学长问我,dijkstra算法能处理负权边问题吗? 我不知道,回答的可以,学长跟我说是不可以的,当时也没在意,谁知道现在复习才发现Bellman-ford算法才能处理负权边问题,这个后面回写一篇博客总结一下. PS:数据结构这课我最后还是考了100,由此,分数或成绩并不能衡量一个人技术水平的高低.

上交软院

这是我参加保研夏令营去的第一所学校,也给我留了很深的印象.

上交的软院很小(比起大工的来说),但是校区很大,而且建筑设施都很不错.听完院长的介绍我才真正对上交的水平有所了解,实际上我对所有的学校基本都没什么了解..

后来参观实验室,对上交实力最强的IPADS实验室很感兴趣,他们主要是弄内核方向的,而这也是我本科阶段很感兴趣的一个方向,我立刻把答辩的题目换成了IPADS实验室的题目(之前选的是一个机器学习的老师的题目).看了一篇Nested Kernel的论文就去答辩了,由于临时换题目,只看了两天,只能说对内嵌内核这东西有了个表面上的理解,答辩完自我感觉还行,但是最后收到的通知是待定..

后来陆续给上交软院打过两个电话,都说现在结果出不来.最后知道今天(9.28)我填上了清华的志愿后,才有一个老师打电话来问我还想不想去上交.无奈已经错过了,其实能去上交的顶级实验室玩自己喜欢的方向对我是很有吸引力的,如果上交早一点确定了要我,说不定我就不会去清华了.可是怎么可能事事都顺意,也正是这种挫折感让我坚定了去清华的信心.

中山-CMU 电面

中山大学和卡内基梅隆大学的合作项目,一年中山大学,一年卡耐基.

卡耐基梅隆大学应该是每个CS专业的学生的梦想吧,尤其是他们的<深入理解计算机系统>这门招牌课,我一直想去听一下.所以报了这个项目.

电面很简单,一群CMU的老师问了我几个问题,10分钟就结束了,由于英语说得不好,我答的也磕磕巴巴,问题问的还是很深的,比如STL里面map后的数据结构,摄像机的标定等等..要不是我选过虚拟现实这课,我可能连calibration是什么都不知道..

最后还是收到了offer,但是拒绝了,因为他们只肯给我985学生都有的15w入学奖学金.我希望读研不要花家里的钱,另一方面我觉得他们并没有对我很认可,或者我自负地觉得自己值得更多..

上科大计算机

上海科技大学,中科院刚成立的一所大学

我是在学校的宣讲会上面对这个大学有了解的,当时我只有北航的一个offer,就毅然决然的报了名,当时想的是拿来保底.但是这学校实际上很不错,都是一些海归的大牛当老师,最后我对象去了那里.

这个大学很人性,都是电面,三个老师面试,面试上科大的时候我已经”身经百战”,面试能力达到了巅峰.答得都挺好,包括美赛获奖经历,一些项目上的问题,还有专业课的知识,值得一提的是,两个老师都问了我快排的问题,在中科院计算所的笔试上还考过手写快排的问题,可见快排真的是百问不厌的经典算法,值的深入理解一下.

最后收到了offer,由于不是985,211,家里不让,再加上有了清华的offer,还是拒绝了

清华软院

我没有清华梦

我学生时代考不上清华,我也没想过去清华读书,但是没想到我竟然能有机会去清华读研,还是百里挑一的学硕..

我们学院去年有很多学长去了清华软院,所以我根据他们的经验对清华软院了解的也比较多,虽然清华软院没有夏令营,但是只要获得了复试的资格,还是很容易进去的.

我最终进入了复试,但是听说我们学院日语强化的第一名今年由于六级没有通过没能获得复试的资格,我的经历和其他人的经历比起来也显得不那么坎坷了.后来一比才发现,我是同行的所有软院的去清华复试的人里面成绩最差的,我没怎么紧张,毕竟奋力一搏.

复试当天上午机试,三道题,用VS敲,上面还有VA,我平时就用这个,环境方面没有什么问题.第一道题暴力模拟,比较简单,第二道题DFS,一个递归就可以.第三道题我做的时间比较长,最后想出来了一个动态规划的算法(这得益于前面51nod的动态规划的教程).做完了之后我没有直接离开,因为离开了我也没地方去,我就一遍一遍地看代码,没想到还真让我找到了一个小bug(将矩阵读成了方阵),后来我又坐在那里准备面试的自我介绍,这样,到最后交卷我才走.

面试进行的也很顺利,清华的教授们都很nice,我自我介绍的时候一直点头,尤其我说道开发的游戏和网站的时候老师眼前一亮.无奈一个老师突然问了我网络的七层模型(OSI),这个我只记得五层,就直说了五层模型,其它的问题都没啥问题.

后来打电话询问居然过了那边的学硕,老师说我机试做的好才给我调了的.真是瞬间感觉之前刷题的努力都没有白费

其它

其实还面了其它一些学校,这些面试大都没什么营养,经历也都各种各样,简单提一句.

北大,这个我夏令营材料就没通过,后来联系老师去面了一下,到了那里,联系的老师对我的自我介绍就不满意,倒是离我最近的老师问了我一些问题,包括支持向量是什么等等,我也都答了,后来还是没有通过.9月正式推免我又投了一次,材料还是没有通过..

北航,我去了北航计算机学院的夏令营,说实话这个夏令营让我感觉北航其实没我想的那么好,机试题目很简单,面试问的问题也都是一些项目经历.但是最后因为没有offer,一直拖着没给北航回复,感觉也是挺对不起这个学校的.

中科院计算所,这个是当时北航要确认,我有点慌神,就报了一下,但是我并不很想去这种和校园不太一样的研究所.后来收到面试通知我还是去了,面试老师问的问题五花八门,从项目经历到家庭信息,就是没问专业知识..期间老师还暗示我这个方向并不是很赚钱..后来面完了老师又让做一个笔试,题目量很大,编程要求手写快排和二分查找..不过中科院效率很高,下午就让我去签字,我跑到那边发现是要签一个保证去中科院的协议,果断放弃掉了..

现在,我已经填完了推免申请,等待清华的确认,同时也在找清华的导师收留我,同时还在找实习..

我之前一直想着保研完了就可以放松了,但是我发现我早已停顿不下,来到了一个驿站又到了走向下一个驿站的路上..

第五章 优化程序性能

这一章主要讲的是编译器对代码的一些优化策略,包括在代码效率和代码在一些极端状况下的准确性的权衡.以及用具体的汇编代码及在机器中的实现来说明一些代码习惯的对程序效率的影响,最后介绍了一种unix环境下的程序剖析(profiling)工具GPROF.

优化程序的效率时,除了优化整个算法的时间复杂度,其中编译器对代码的编译也起到了至关重要的作用,而编译器除了要将代码变得更快,还需要考虑程序的正确性,开头的例子给出了一个对源代码非常明显的优化,但是编译器却不敢执行这个优化,主要原因就是他不能保证这个优化过的结果和没优化的结果是一样的,事实上,在极端情况下,优化后的代码可能会产生和原来的代码不同的结果.

所以,编译器的一些优化级别,需要保证对程序只使用安全的优化,也就是保证优化后的代码和之前的代码完全相同,这种保证就会使得一些明显的优化无法执行(因为无法保证极端情况下的正确性).

接下来以一个程序(P330)为示例,讲了几种写代码时的优化策略

消除循环的低效率

这个说的是可能编程中经常会遇到的问题,循环 for(int i = 0;i<vec_length(v),++i) 如果这么写的话,每次循环结束都会调用 vec_length() 这个函数来确定是否到达循环结束,对于长度不变的数据结构的遍历,每次循环结束调用的这个函数的开销是不必要的,应将其避免

减少过程调用

这个部分说的是尽量不要在循环中循环调用一些函数,在循环外拿到需要循环遍历的数据结构,然后再循环中直接去调用数据结构.

书中也提到了这种做法不太符合程序模块化的要求,只有在追求效率的代码中会用到,这种情况也应该写几行注释注明.

消除不必要的存储器引用

讲的是,这么写

for(int i = 0;i<length;++i)
    acc = acc OP data[i];

和这么写

for(int i = 0;i<length;++i)
    *dest = *dest OP data[i];

前者更好,因为,前者在汇编中实现可以用寄存器存储 acc ,而后者是个指针,汇编中只能用存储器实现,每次去地址再取指会浪费大量时间.

优化程序的两个限制:

1. 延迟界限: 从开始到结束完全完成一条指令所需要的时间决定,达到这个界限的原因是下一条指令需要上一条指令执行完毕才能执行,指令间有严格的操作顺序.
2. 吞吐量界限: 指令之间可以完全流水线化(fully pipelined),这样使得硬件的功能达到了最大的利用率,在这种情况下优化只能优化处理器功能单元的原始计算能力了.

一些编译器可能做的优化

循环展开

就是循环每次原来读一个数,优化后每次读 k 个数,这样循环的次数就变成了 [n/k] 次,这样优化结果性能的提升得益于 减少了循环的开销工作 ,比如原来累加器 iter 原来要累加 n 次,现在只要累加 [n/k] 次了, 降低了开销操作的数量.

提高并行性

这个比较容易理解,比如一个累加的程序,原来只有一个累加器,每次加一个数,改成并行的可以有 k 个累加器, k 个累加器同时工作肯定要比原来效率高

不过这里硬件会成为限制条件,后面就提到了寄存器溢出这种情况,就是累加器多得在寄存器里面存不下了,只能到栈里面存,这样又增加了存储器开销,反而会使效率下降.

重新结合变换

就是利用有结合律的变换,运用一下结合律,比如把下面这个

acc = acc OP data[i] OP data[i+1]

变成下面这个

acc = add OP (data[i] OP data[i+1])

代码层面没有改进,但是从汇编层面分析,原来每次循环在 acc 上的运算 由原来的两次变成了一次,这样就缩短了关键路径,从而提高了效率.

上一章可以看到分支预测会对程序效率有很大影响,因为是一个完全投机的预测,预测错了下面所有取到的指令都应该放弃,这会造成比较大的损失.但是这也是不可避免的,文中提到了 1. 不要过分关心可预测的分支,我们预测分支往往会执行是因为,再循环中,这样的预测策略只有最后一次会失败,所以几率还是比较大的 2. 在程序猿的角度,将分支跳转指令改为条件传送指令( val = exp?a:b; )往往能取得比较好的效果,因为条件传送指令不会有错误的开销: 在流水线中,下一条指令译码钱,上一条指令已经完成了执行操作,因此下一条如果是条件传送指令的话,刚好可以通过转发机制得到状态码.

加载和存储

读和写都制约程序的运行效率 如下:

1. 加载相关, 循环两次之间的读有相关性,下一次的读需要上一次读出来的结果,所以下一条读的指令必须等上一次循环完全结束
2. 读写相关(write/read dependency), 一个存储器读的结果依赖于一个最近的存储器写.这个是经常会遇到的问题.

读写相关的解决方案 (P366):

在存储单元中有个存储缓冲区,包含将会写到存储单元的,但是还没完成的操作(地址,值). 每次读的时候 (load 指令)会先检查一下存储缓冲区,如果发现读的地址在存储缓冲区里面(说明呆会会被写进新值),就直接在存储缓冲区里面拿新值了.

…其实上面的操作就是转发

最后 程序剖析(profiling)

这里介绍了一种分析程序效率的工具,GPROF

1. 在编译和链接过程中加上剖析的指令 gcc -o1 -pg prog.c prog
2. 执行程序,会生成一个多余的 gmon.out 的文件 ./prog arguments...
3. 使用GPROF来解析这个out文件(必须有out文件才能解析) gprof prog

今天刷题的时候遇到了一道中国剩余定理的题,当年在网络安全这门课上学过这个算法,但是到现在只记得这个名字了,就回去翻课件回顾了一下,结果发现了很多知识点,就在这整理一下.

乘法逆元

乘法逆元这个概念最初是在离散数学中引入的, 而在离散数学中提到的是范围更广泛的逆元. 是在代数系统里面提到的这个概念 定义如下

令e为S中关于某二元运算的单位元.对于x∈S,如果存在yl（或yr）∈S使得(yl)x=e（或x(yr)=e）,则称yl(或yr)是x的左逆元(或右逆元)。若y∈S既是x的左逆元又是x的右逆元,则称y为x的逆元。如果x的逆元存在,就称x是可逆的.

在这里,二元运算就是模p乘法,p就是整个集合的范围.在这里,如果w是Zp中的某个数,我们求w的乘法逆元,这里有一条定理.

Zp中的任一整数w有乘法逆元当且仅当w和p互素

这里可以简单证明一下必要性,w和p互素,我们可以用w乘Zp中的所有元素,得到的剩余类是Zp中所有元素的另一种排列. 以上这句话可以用反证法来证明 假设乘完得到的剩余类并不是Zp的另一种排列,说明得到的剩余类中必定有两个相同的数.设为m,则:

k1*w = s1*p + m
k2*w = s2*p + m

所以

(k1-k2)*w = (s1-s2)*p

因为w和p互素 (k1-k2)应该等于p,而k1,k2都小于p,得到了矛盾.得证.

现在知道了,如果求乘法逆元,要求这个数应该和基数p互素,下面看怎么求乘法逆元.

Euclid算法

Euclid的扩展算法可以用来求乘法逆元.先来看一下基本的Euclid算法. 整个算法写起来很简单

gcd(a,b) = gcd(b,a%b)

证明起来也很简单,具体看<密码编码学与网络安全>P74 这里说一下扩展的Euclid用于求乘法逆元. 就是假设 gcd(a,b) = d, d 能写成 a和 b的组合形式 d = xa + yb 这样,当x,y互素的时候,明显d == 1,可以得到x是a的乘法逆元,y是b的乘法逆元. 具体x和y的推导计算可见<密码编码学与网络安全>p81

中国剩余定理

这个才是重点,首先中国剩余定理(Chinese Remainder Theorem)的意义是说明某一范围内的整数可通过它对两两互素的整数取模所得的余数来重构.

具体证明如下

深入理解计算机系统这本书大二的时候就买了,因为有很多学长推荐,而且很多计算机名校也用它当<计算机组成原理>的教材.但是由于各种原因一直拖着没读,大三利用寒假读了一下,感觉受益匪浅,但是没有读完,大三下学期断断续续不仅没有继续读,还把前面读了的忘了个差不多,现在准备利用暑假读完,并记一下笔记,以防忘记.

第四章 处理器体系结构

这一章主要是将前面几章的理论用于实践,通过一个相对简单的”Y86”指令集,介绍了机器代码,汇编代码之间的关系,指令流水等概念.

Y86指令比较简单,只实现了一些基本的指令,指令和数长无关,默认立即数都是4个字节,指令是变长的…

• 立即数用小端(little-endian)编码,比如 0x12345 变成4字节应该是 0x00 01 23 45 但是存储到内存里面就是 0x 45 23 01 00
• 数的运算指令会设置条件码 ZF SF 和 OF (零 符号 和 溢出)
• 程序状态码 Stat 代表了程序运行状态(AOK, HLT, ADR, INS),当程序运行不是AOK时,会进入异常处理程序
• 调用一个函数先写的参数会距离栈顶更近,比如一个函数 int sum(int* Start, int Count) 取得传进来的指针Start值用的是 8(%ebp) 取Count值用的是 12(%ebp), 所以,调用的时候, 需要让后面的参数先入栈
• 完整的汇编代码中,开头会指示这段代码的开始地址,结尾会指示这段代码栈的栈尾地址(栈向低地址增长),整个程序就在两者之间运行,所以要保证栈不要增长的太大覆盖了程序代码
• pushl %esp 和 popl %esp 的选择
  • pushl %esp : push本来就要减少栈指针esp,而push esp又要将栈指针压栈,最后的结果就有两种情况 :
    1. 压栈的是减少之后的esp
    2. 压栈的是原始的esp
  • popl %esp : 同上,有两种情况 :
    1. esp中存的是原来的esp指向的值
    2. esp中存的是增减完了的esp指向的值

  在Y86中,压入的是原始的esp,弹出的是原始的esp指向的值(具体可以看254页的分段伪代码)

• 存储器和适中:
  1. 时钟寄存器: 不是%esp这些寄存器,是输入值到输出值由时钟控制的一种硬件
  2. 随机访问存储器
     1. 寄存器文件: 里面包括8个程序寄存器(%eax,%esp),对外提供程序寄存器的读写端口
     2. 虚拟存储器系统:也就是内存

顺序实现Y86

将指令分为六个阶段,每条指令顺序执行,上一条指令执行完最后一个阶段之后才会执行下一个阶段,执行效率低下.

• 取指 : 取指令,根据PC获得icode(指令代码)ifunc(指令功能)寄存器操作码,valC(常数).
• 译码 : 通过寄存器文件及上一步的寄存器操作码得到相应寄存器的值
• 执行 : 执行需要的运算(加减,异或,与),并设置条件码
• 访存 : 访问内存,读或写,比如一些 irmovl , push(栈) 等指令会用到
• 写回 : 将在访存阶段或者执行阶段得到的值写到存储器里面,用到的硬件和译码相同,都是寄存器文件
• 更新PC : 根据指令得到下条指令的地址

两条指令 : call指令运行会将下一条指令的地址压栈,方便返回 ret指令用栈顶的值来更新PC,解释了一个函数运行的经过.

整体执行是用时钟控制的,每次时钟由低到高都执行一个阶段.

寄存器文件有两个写的端口,如果想要对同一个寄存器写的话,只有有限制高的端口会执行写操作,这样做也是为了解决上面说的 pushl %esp 的问题,在指令执行过程中,寄存器文件的两个写端口分别分配给 1. 访存得到的 valM 2. 计算得到的 valE 而pushl %esp 指令刚好这两个都要写esp ,所以需要制定优先级,具体的优先级不同的编码实现不同.

流水线Y86

书中对流水线的解释很到位

…(顾客点餐)通常都会允许多个顾客同时经过系统,而不是要等到一个用户完成了所有从头到尾的过程才让下一个开始.

当某些流水阶段理解晦涩时,可以对比顾客点餐的例子.我是这样理解的: 每个阶段每个时钟都执行不同的指令,比如取值,每个时钟取一条,比如译码,每个时钟译码一条..

使用流水线来处理指令需要流水线寄存器,就是用于每个阶段之间存储的硬件,上面存储的是这个阶段之前,这个阶段需要执行的指令所需的值. 比如访存流水线寄存器(M)里面存储了访存需要的地址,以及上一步运算得到的状态码等等信息.

在276页中的 E寄存器下面可以看到一个叫 Select A 的硬件,它是为了节省存储空间出现的, 在流水线系统中, value A将不止用来存储在寄存器A中得到的值,还用来存储 1. Jxx 不需要跳转时的 valP 2. call 的 valP (需要将本来的下一条指令的地址压栈) 3. irmovl 中本来就需要存的 valA 由于各个指令并不冲突,所以可以共享存储..具体用操作码来区分.

流水线需要解决的一些问题

流水线冒险

两条指令相邻执行,第二条指令执行到译码阶段的时候第一条指令还没执行完,甚至更前面的指令还没执行完,当某条指令的执行需要前面某条指令计算完的值的时候会出现这种问题,有可能会取到错误的值.两种解决方案: 1. 暂停,暂停当前指令等待前面会影响到后面的值的指令执行完(通过插入bubble) 2. 转发,后面的指令用到的值可能在前面的指令中已经计算并存储了下来,只是还没放到寄存器里面,这时可以根据不同的情况直接在前面指令的存储设备里面获得需要的值,而不是在寄存器中取(错误的值).

• 转发有一种情况解决不了,就是两条指令相邻,上一条指令要到访存阶段才能得到正确的值,下一条指令在译码阶段就需要该值,这样就结合暂停的方法,暂停第二个指令,等到第一个指令得到了需要的值再继续执行.
• 另外还有转发的优先级,这个比较容易理解,就是离当前指令越近的指令的指令寄存器优先级越高

异常处理

当某条指令出现异常的时候,后面的指令有可能会更新程序员可见的状态(状态码),必须禁止,比如当访存或者写回阶段出现异常的时候,需要将执行阶段的信号 set_cc (允许设置状态码)设置为0,就是不允许后续的指令修改状态码.

ret指令

遇到ret指令的时候,需要访存结束(得到返回的地址)才能确定下一条指令的地址,在此期间流水线是一直运行的,需要在ret运行后连续3个周期插入bubble,直到可以得到正确的下一个指令的地址(P297)

预测错误的分支

对于一些分支跳转的语句,Y86会预测始终选择分支,但是这明显不一定是对的,当分支跳转的指令执行到 执行 阶段的时候就可以验证分支跳转的条件是否成立,如果预测正确就能正确执行,如果预测错误,需要”取消”取出来的多余的两条语句,也是通过插入气泡的方式,同时在周期5可以取出正确的下一条语句(P298)

PC选择

在流水系统中,PC选择是第一件事,PC有三种选择 1. 刚才提到的分支预测错误情况下, PC选择M_valA中取出预测错误的指令的 valP 当做下一条,因为预测错误,就要执行本来计算好的 valP (下一条指令)了,至于为什么存在 valA里面,前面有说明.. 2. 刚才提到的ret指令,需要在 W_valM 中获得下一条 3. 其它情况采用预测值 预测策略刚才也提到了,遇到分支的情况,总是预测会跳转,没有分支直接计算下一条.

距离上次写博客已经过去了半个多月,我兴致勃勃迁移博客的热情也减少了很多,从开学充满激情海投简历到现在也认清了自己的水平,昨天受到腾讯大连HR的启发,准备对自己的人生进行思考,规划自己的生涯.

过去的二十多天里,发生的事情有很多,比如我拿到了人生第一份实习offer-去哪儿网的offer,比如寒假的数模成绩终于出来,拿到了M奖,比如终于决定保研,开始复习数学,练习口语,比如报名叉院的硕博连读,考核用到机器学习的东西,又要重拾机器学习,比如一些课结课了,我却觉得收获甚微,比如热火近六年首次无缘季后赛…时值期中,开学第二个月末尾,希望总结一下,以便之后的提升.

找实习

找实习这事儿,一开始看的很重,因为自认为水平还不错,至少和身边的同学比起来总是有一种膨胀的优越感,因为做编程作业时,我总是比大部分人快,需要学新东西我也比很多人学得快.事情开始了才认清自己的水平,虽然成绩不错,但是到了面试阶段根本不看你的成绩,虽然有一些项目经历,但是做的项目都太小,拿出来一说面试官根本不放在眼里.导致阿里电面和豆瓣电面都以失败告终,还有很多公司直接在简历投递阶段被刷了下来..就连之前信心满满的腾讯,居然笔试都没过,身边挺多同学都过了,就我没过,笔试题上面的问题我很多都会并且有信心答对,这份试题我做完感觉是能够体现我的能力的,没想到没有通过,对我的打击也很大.看看身边的同学,反而是那些项目做得挺好的拿起offer来毫不手软,基本上都是一个电面就能搞定.

后来终于等到了机会,有机会现场面试去哪儿网,一行人奔波来到本部,我吸取上次面试交流生的教训,特别注意穿着,但是现场还是有点紧张,不过面试官人真的很nice,遇到我想不到的问题直接说,没事随便说..开始先说三道笔试题,第一道是循环数组找元素,leetcode上面有原题,我说完之后,他问我你这二分取中间值

int mid = (low+high)/2;

万一溢出了怎么办?我当时没想到..说了比较复杂的两个方法,暴力转到longlong和先用double分别除2加起来在强转回int,他笑着说,直接这样嘛

int mid = low + (high-low)/2;

想想昨天还和对象讨论过这两种写法..后面又说到了我当时没做出来的第三题,面试官让我说了一下思路,又问了我一下时间复杂度,我说了个最坏的,他又问我平均的..又没说出来,接着问项目,他说在你项目里面挑一个最熟悉的吧(估计是看我写的比较多),我直接说简微博那个,听我提到接SDK,就问起了OAuth认证,我去正好啊,之前刚看了一遍,我就说了一遍,他又问我为什么要通过两次申请才给你权限,为什么不一次直接返回token,这些我都不会,只能随便猜,后来他看我懂一些机器学习,又问我为什么用SVM.什么情况下用SVM,这些高大上的问题我显然也不会..但是最后他居然给了我offer,直接让我去HR那里报个到..后来顺利拿到

后续

到现在我倾向拒掉这个机会..首先去那基本是写java,虽然我不排斥,现在还是希望在大四提升自己的C++和python能力,然后是我加了实习交流群之后群里面同学表现出来的水平也让我深深的担忧..老是问一些基础问题,倒不是我逼格有多高,我担心的是去到连函数也写不上的公司或者并不能锻炼我能力的公司对于实习确实没什么意义..但是真的感谢这个公司和很nice的面试官,毕竟他们是我投的十多家公司里面唯一肯定我的一家..

这周末去面阿里,听同学说哈尔滨站刷了很多人,估计是内推招了不少,这个网申直接提高标准了,不管怎样还是加油复习,毕竟这是我近期最后一次面试了.

做比赛

开学比较重要的一件事就是准备”微软创新杯”,因为很早报了名,但是一直没准备,只好开了学加快速度赶工..整个游戏大概写了两周,主体代码大约两天就完成了,但是做出来多少有点成就感,比赛截止日前两天才听旁边实验室开始动工,他们拿了去年的项目修改一下直接参赛..而且听说一个项目他们连续拿去参加了好几届,最后校内评选我们意外落选..听负责人说要6支队伍,我们排到第7..而且排名是旁边实验室老师一个人定的,当时简直失落的不行

后来准备把游戏投到腾讯比赛,这个现在还没开始弄..

然后就是寒假数模得了个M,这次获奖没什么兴奋,因为应该算是我们努力几乎半个寒假的产物吧,然后周围有听说了一些H奖和F奖的,也觉得自己的奖没什么,不过这个奖多少让我心里石头落地

然后是英语竞赛,上次我以一分之差失去机会,这次成绩没出来但是感觉做的也尽力了..

保研

这也许是我最近看的最重要的事情了,因为找实习都困难,离我预想的有比较大的差距..只能尝试再用几年锻炼自己,而且我在后几年有比较清楚的目标,就是熟悉linux系统,然后弄几个github上的好项目练手,然后写点大的项目,比如写个python框架,要学的东西还有很多,直接去工作可能会学到不少实战经验,但是空余时间可能不足使我提高自己,或者说学我想学的.

咨询了几个学长,学姐,看了很多经验贴.去年学院大丰收,清华北大去了9个,有一些成绩和我差不多的学长都去到清华软院,但是学长都很努力的准备了保研,包括刷题练英语,早上六点晚上十点,我感觉我的努力程度还差很多,而且面试这种我还是觉得需要运气,毕竟需要得到看好你的导师不是那么容易.于是我开始复习数学,开始练口语,并尽力形成routine,但是事情太多也总是耽搁.

Last

昨天听到腾讯的HR和我们交流就业经验,听他口里的找实习和工作包括跳槽一切都显得这么理所当然,可能每个时期都有每个时期想要的,也都有各自的迷茫,只有经过了某个阶段才能对自己的过去侃侃而谈.最近我一直在被上面的事情们包围着,心情也低落,因为好像我失去了重心,被生活推着走.突然好像我什么也干不成,突然好像我一直失败,这可能是我准备的太多又过度关注周围的原因.找到合适实习的大牛现在正式过上了享受的大三生活,每天打打球,看看书,轻松惬意.我却要为了保研复习,这样比起来虽然并不公平,但是是因为我们追求的不一样,他们为了这种机会一直在朝这个方向努力,而这也是他们想做的.所以我也要找到自己想做的.

我承认技不如人,所以我需要学习,我希望自己可以找到自己想要的生活.我希望规划好我的生活,腾讯HR说,年轻比offer,年长比健康,比来比去比的都是生活,我不希望自己拿自己的生活和别人的生活相比,也不希望自己陷入和别人以收入攀比的怪圈,更不希望用offer定义我的价值.我希望的是以后我的工作是我喜欢的事情,或者我能过上我想要的生活.

我想要的生活是什么样子呢?我忽然想起来以前去海贝广场那边的海边,夜晚走在安静的小区的时候.我觉得我的生活需要学习,需要奋斗.所以,但求能够学到东西,能有那样的夜晚.

所以我需要5年计划和3年计划,如果我后续生活是专硕,我应该如何利用剩下的在学校的3年?如果是硕博连读,我应该如何利用剩下的在学校的5年?

1. 所有准备用于提高自己的专业书籍尽量看英文的
2. 数据结构和算法是核心(1.c语言描述 2.算法导论)
3. 精通一门语言(视情况而定,排序如下 1.C++ 2.Python 3.Java)
4. 熟悉linux系统,至少读一下源码
5. 做一个拿得出手的东西(操作系统,编译器,框架,应用…)
6. 为开源项目做贡献,持续更新github
7. 持续锻炼,别死的太早- -

之前学习git的过程中就遇到了这个问题，电脑并不能使用ssh连接远程仓库，例如clone git@github.com/xx.git 这样的工程会失败。我就必须改成使用HTTPS协议，把连接改成 https 的，或者直接配置一个环境变量

git config --global url."https://".insteadOf git://

这样处理有一个弊端，我在Ubuntu上面任何时候需要连接远程仓库，必须输入我的用户名和密码，这样有点麻烦，而SSH协议是用本地存储的公钥私钥验证的，只要配置好了就不用输入用户名密码，我决定改成SSH连接。

原因

电脑无法用SSH连接远程仓库的原因是SSH协议用的是22端口，但是有些防火墙会把这个端口block掉

解决方案

既然不让用22号端口，换个端口就可以了，就像上面stack overflow的解决方案一样，改用443端口，在 ~/.ssh/ 建立一个config文件，写上

Host github.com
User git
Hostname ssh.github.com
PreferredAuthentications publickey
IdentityFile ~/.ssh/id_rsa
Port 443

这里还有个坑，就是建立的这个config文件不能太公开，否则git不答应，使用

chmod go-rw ~/.ssh/config

这句话就是把g（group当前组）和o（other其他用户）的对config这个文件的权限去掉读和写。

两个有用的文档

1. git里面用命令行更改远程仓库的URL/使用的协议
2. 用https的端口（443）代替被封掉的ssh端口（22）

后续

修改完这些。。我以为一切都结束了，可视连接远程仓库还是连接不上，这时候我发现在我项目目录下的 .git/config 里面，远程仓库的地址写的是git://github.com/xxx.git,并不是ssh里面标明的 git@github.com/xx.git 的形式。 那么问题来了，git:// 和 git@有什么区别？ 进过一番查询，找到了一个解释的比较清楚的答案

It depends on the repository. The native git transport uses TCP port 9418. However, git can also run over ssh (often used for pushing), http, https, and less often others.

You can look at the repository URL to find out which port it uses. Notice that many public repositories have several alternate URLs; for instance, the kernel.org repositories have git://, http://, and https:// URLs.

The common URL schemes for git repositories are:

• ssh:// - default port 22
• git:// - default port 9418
• http:// - default port 80
• https:// - default port 443

If the URL does not have a scheme, it it using ssh with a slightly different syntax.

See the git fetch manpage for more details on the available URL schemes.

大体意思就是git://使用的是 native git协议，用的是9418端口，有些防火墙会封掉，而git@也就是ssh:用的是ssh协议，端口是22，也会被一些防火墙封掉，上面那些操作只能解决ssh连不上的问题，也就是说执行了上面的配置，只能保证git@github.com这样的远程仓库能连接，而写成git://就无法解决，解决这个，只能利用git的全局配置把所有的git://连接转成https://连接，这样就避免了使用native git协议。 这篇文章对上面的问题说的挺好。

前言

最近在读侯捷老师的《STL源码剖析》一书，收获简直太大。一激动就想把学的东西赶紧记下来写篇博客，然后想到我以前的博客系统，bug无穷，于是决定亲自配一个Octopress的博客，因为之前的博客是Jekyll的，博文都用的markdown写的，Octopress也是markdown语法，这样可以直接连文字带样式轻松移植过来，想的挺轻松，但是实际操纵起来简直折腾了我好几天。。

在octopress上面搭建博客的过程真的是一波三折，由于原来简介的jekell模板有点问题，我决定把自己亲手重新装一个octopress的博客

双系统的问题

首先，由于双系统，我希望我能在任何一个系统上面写博客并同时push到github上面，由于octopress博客写完博客需要生成一下，我就不得不在两个系统上都装上生成博客需要的ruby环境和javascript环境。

装ruby的一些包时候遇到了一些问题，由于GRW的问题，直接从远程仓库安装安装不了，这时候需要借助淘宝搭建的一个国内的仓库，15min一更新还是很快的

使用如下的命令就可以了

$ gem sources --remove https://rubygems.org/
$ gem sources -a https://ruby.taobao.org/
$ gem sources -l
*** CURRENT SOURCES ***

https://ruby.taobao.org
# 请确保只有 ruby.taobao.org
$ gem install rails

博客主题的选择

octopress对于主题的安装还是很简便的，调了一番，终于找了个比较中意的主题 classic-martinb

$ cd octopress
$ git submodule add git://github.com/fapper/classic-martinb.git .themes/classic-martinb
$ rake install['classic-martinb']
$ rake generate

linux下面我的博客无法找到

不知道什么原因，我的博客在linux的系统（包括我的ubuntu系统和安卓手机）的浏览器上面加载不到。。 后来我发现，我的博客域名是d-w-.github.io，在linux下面ping都无法ping通，应该是三级域名结尾是 - 的原因，我试了一下，只要结尾不是 - ，都可以ping的通。。这个问题还等后续解决，比如买个域名撘过来。。我甚至想把github的用户名给换了

更改了主题或者更新了博客后 rake deploy 的push被rejecte

这个问题一直出现，在stackoverflow上面有各式各样的解答，都可以起到作用，但是我每次deploy都要按照上面的方法执行一遍岂不是太麻烦了。。我观察了一下，原因应该是远程分支有两个，git并不知道push到哪一个的原因，又看了一下octopress的文档，有这么一句

Note: With new repositories, Github sets the default branch based on the branch you push first, and it looks there for the generated site content. If you’re having trouble getting Github to publish your site, go to the admin panel for your repository and make sure that the master branch is the default branch.

看来只要master branch设为了默认分支就好了，这个是不是合适的解决方案还待后续检验。 后来经过我无数次删除repo，重装的循环，终于发现了原因。。是因为windows和Linux的换行符不一样，比如我在Linux下面初始化了一个repo，换行符是LF，然后我到了windows系统下面打开了这个项目目录，想去push，但是windows上面换行符是CRLF，这时候和远程的仓库比对，发现换行符不同。。就会被rejecte，因为git不知道用哪个好。。解决的办法在stack overflow上找到了，只要改一下配置就好，看来git确实强大。

git的SSH验证和HTTPS验证

由于端口的问题，我这边并没有开SSH的端口，都是采用HTTPS验证，在windows端可以直接用github的桌面版，push起来也挺轻松，但是在linux端，由于是HTTPS验证，每次push都要输入用户名和密码，这个问题待解决。

对第三方主题进行更改

既然折腾了就要折腾到底，单纯clone一个别人写好的主题显然不能满足我的要求，毕竟我以前的博客就有一些不错的特技。所以要对fork过来的第三方主题进行改装，来到 .theme 文件夹下面的相应的主题包里面，进行需要的修改，这里需要注意的就是修改结束之后需要再

rake install[name]

一下，这样所做的修改才会生效

添加多说评论系统

这个比较简单，参照了为 Octopress 添加多说评论系统这篇文章，需要注意的一点是文章需要在前面的yml上面注明 comments: true 。

在文章中添加本地图片

这个是因为我用了泰然网上的两个图片，没想到有防盗链。。只能下载到本地才能正常显示，当然我在文章里面注明了图片的出处，个人认为这种防盗链确实没什么必要。。 参照Octopress在页面和内容中加入代码、图片、带标题图片方法 图片放到 octopress\source\images 里面 通过

    r'<img src="/images/pic_name.png">'

引用就可以了。

Monster Storm

边学边写的cocos2d-x游戏,基于3.0版本

这个游戏的主要难点有两个 1. 怎么把所有需要消除的精灵摆对位置 2. 怎么找到某个精灵周围的同类精灵

摆放精灵

1. 找到精灵摆放点的左下角的(x,y)坐标,这里直接借用泰然网教程上说的

m_matrixLeftBottomX的值 ＝ （ 屏幕的宽 － 寿司的宽＊N个寿司 － （ N-1 ）＊寿司之间的间隙） ／ 2。

1. 从下到上,从左到右遍历整个matrix,为每个精灵编号,例如,左下角的精灵行号0,列号0……这样每个精灵都有了一个坐标,而每个坐标对应了屏幕上的一个位置,只需要根据左下角的坐标加加减减就可以得到某个坐标对应的具体位置,这样就建立了坐标和精灵,坐标和图上的位置分别以一对应的关系.
2. 有了上面一一对应的关系,只要在对应位置的上空XX米创建出来精灵,并把它移到对应位置就可以了

查找并消除精灵

1. 定位到用户点击的精灵,想完成消灭小星星的消除,首先要知道用户点了那个精灵,这里我当时写的算法很low,是先获取用户点击的坐标,然后遍历整个精灵matrix,看一下哪个精灵所在的square包含了那个坐标就是点击的坐标,当然,已经被消除了的精灵是不在那个matrix里面的;
   • 比较好的一个做法应该是根据点击的坐标和左下角的距离关系直接找出对应的位置,然后检查该位置是否有精灵..
2. 定位完了就要找该精灵周边同类的精灵了,寻找过程类似于深度优先遍历,我是用递归写的,比如对于定位到的精灵,分别找它上下左右的精灵,如果上下左右的精灵是同类的话,就加入list,并更新上下左右的精灵为当前的精灵,继续递归查找上下左右.注意:查找的过程要注意重复,每次找到新的都要判断一下是否已经找过当前精灵..
   • 当前另一个想法是类似于广度优先遍历,,用一个队列来维护,广度优先的好处是避免了递归
3. 然后要判断一下用户的第二次点击,点击的是不是第一次点的那个区域,判断的方法就是得到第二次点击的精灵(的地址),和已经存到list(第一次点击之后的所有同类精灵)里面的所有精灵进行比较,如果有相同的,则True,不是就False,清空list,blabla…
4. 点击完了,也消除完了相应的精灵,要完成上面精灵的下落和精灵列的左移,这在泰然教程上面说的很清楚

注意由于游戏不同,这里只有过程一,也就是不必填充,只让上面的下落:对于每一列从下到上查找空白数,等到了空白数大于0就说明精灵要下落了

  // 从下向上
    for (int row = 0; row < m_height; row++) {
        sushi = m_matrix[row * m_width + col];
        if (NULL == sushi) {
            removedSushiOfCol++;
        } else {
            if (removedSushiOfCol > 0) {
                //计算寿司精灵的新行数
                }
        }
    }

让精灵列左移也是,从左到右,只要检查每列的第一个元素是否为NULL即可,然后整列左移